#include <stdio.h>

#define N 5
typedef struct Item Item;

struct Item {
    int size;
    int val;
};

Item items[N];

void init_items();

int knap(int cap);



int main(int argc, char** argv){
    init_items();
    printf("%d\n", knap(17));
    return 0;
}

void init_items(){
    int i;
    Item itemA;
    itemA.size = 3;
    itemA.val = 4;

    Item itemB;
    itemB.size = 4;
    itemB.val = 5;

    Item itemC;
    itemC.size = 7;
    itemC.val = 10;

    Item itemD;
    itemD.size = 8;
    itemD.val = 11;

    Item itemE;
    itemE.size = 9;
    itemE.val = 13;

    items[0] = itemA;
    items[1] = itemB;
    items[2] = itemC;
    items[3] = itemD;
    items[4] = itemE;

}

int knap(int cap){
    int i;
    int space;
    int max;
    int t;

    if (cap <= 0) {
        return 0;
    }
    
    for (i = 0, max = 0; i < N; i++) {
        //是否可以放下物品items[i]
        space = cap - items[i].size;
        if (space >= 0) {
            t = knap(space)+ items[i].val;
            if (t > max) {
                max = t;
            }
        }
    }
    return max;
}